<head>
    <meta charset="UTF-8">
<title>算法提高 Graduation Requirements</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <p>【问题描述】</p>
<p>从 Awesome Programmer University 毕业之前，学生们传统上要完成特定的&ldquo;毕业要求&rdquo;。其中之一是开车围绕环岛逆向行驶。对于大多数人来说，这是够疯狂的，但是作为一个额外的挑战，你要看看你能够在环岛逆向行驶多久，中途不停车。</p>
<p>这个环岛共有 N 个路口，均匀地分布在一个圆上。一辆汽车通常会从其中一个路口进入环岛，接下来每一秒，它会逆时针行驶到下一个路口，直到最后到达它的目的地才会离开，中途也不停车。</p>
<p style="text-align: left;"><img src="http://lx.lanqiao.cn/RequireFile.do?fid=r4er9bGj" alt="" /></p>
<p>你一直在观察进进出出的车辆，已经持续了 X 秒。对于每辆汽车，你记录下了它进入环岛的时间和它的进入路口与离开路口。所有的汽车都以 1 路口每秒的速度逆时针行驶。你看到的所有车都会在回到它的进入路口之前离开。这个环岛里有多条车道，所以多辆车可以同时出现在同一位置。</p>
<p>如果你计划得恰到好处，你可以在这个环岛顺时针行驶多久？你必须在一个 &ge; 0 的整数时刻进入环岛，在 &le; X 的时刻离开，并且一旦你离开了，你就不允许再次进入。你在环岛里必须以 1 路口每秒的速度顺时针行驶。你想要尽可能地安全，所以你千万不能碰到或经过另一辆车。特别是，你不能在一个另一辆车正在进入或离开的路口进入，也不能在一个另一辆车正在进入或离开的路口离开，除此之外你可以选择任意的时间地点进入和离开环岛。</p>
<p>记住，你需要在一个可以表示成整秒的时间进入环岛&mdash;&mdash;你必须在整数时刻进入，因此也会在整数时刻到达每个路口。</p>
<p>【输入格式】</p>
<p>输入的第一行给出了数据组数 T，接下来有 T 组数据。每组数据的第一行是一个整数 C，表示你观察的汽车数量。第二行两个整数 X 和 N &mdash;&mdash;你观察的时间(秒)和环岛上的路口数。接下来 C 行描述了你看到的每辆汽车，每行包含三个整数 s<sub>i</sub>, e<sub>i</sub>, t<sub>i</sub> &mdash;&mdash;这辆汽车的进入路口，离开路口和它进入的时间。路口从 1 到 N 逆时针编号(即 2 号路口在 1 号路口的逆时针方向)。</p>
<p><br />
【输出格式】</p>
<p>对于每组数据，输出一行形如&quot;Case #x: y&quot;，其中 x 是数据编号(从 1 开始)，y 是你可以在环岛里行驶的最大秒数。注意，当你任何时刻都不能进入，或者是可以进入，但不能前往下一个路口时，y 是 0。</p>
<p>【样例输入】</p>
<p>5</p>
<p>1</p>
<p>3 4</p>
<p>1 4 0</p>
<p>6</p>
<p>3 5</p>
<p>5 2 0</p>
<p>5 1 2</p>
<p>1 3 0</p>
<p>1 2 2</p>
<p>2 3 0</p>
<p>3 4 0</p>
<p>3</p>
<p>2 3</p>
<p>1 3 0</p>
<p>2 1 0</p>
<p>3 2 0</p>
<p>0</p>
<p>6 4</p>
<p>1</p>
<p>2 3</p>
<p>1 3 0</p>
<p>【样例输出】</p>
<p>Case #1: 1</p>
<p>Case #2: 2</p>
<p>Case #3: 0</p>
<p>Case #4: 6</p>
<p>Case #5: 0</p>
<p>【样例说明】</p>
<p>在第一个样例中，我们有一辆汽车，如图所示。有多种方法使得我们可以逆向行驶 1 秒&mdash;&mdash;例如，我们可以在时刻 1 从 1 号路口进入(我们不能在时刻 0 进入，因为那时有其他车辆)，行驶到 4 号路口(我们不能行驶到 3 号路口，因为我们会经过一辆将要从 3 到 4 的车)。另一种选择是在 0 时刻从 4 号路口进入，行驶到 3 号路口并离开。</p>
<p><img src="http://lx.lanqiao.cn/RequireFile.do?fid=22j2EHq8" width="251" height="252" alt="" /></p>
<p>&nbsp;在第二个样例中，我们可以行驶两秒，在时刻 1 从 5 号路口进入，逆向行驶到3号路口。</p>
<p>在第三个样例中，我们甚至无法进入这个环岛&mdash;&mdash;每秒都有车在每个路口。</p>
<p>在第四个样例中，一辆车都没有，所以我们可以在时刻 0 从任意路口进入，行驶一圈又一圈直到时刻 6。</p>
<p>在第五个样例中，我们可以进入环岛，但是由于只有三个路口，我们将始终与另一辆车相撞，如果我们试图移到下一个路口。</p>
<p>【数据规模和约定】</p>
<p>对于10%的数据，3 &le; N  &le; 10，1 &le; X &le; 10，0 &le; C &le; 10；</p>
<p>对于30%的数据，3 &le; N &le; 10<sup>4</sup>，1 &le; X &le; 10<sup>6</sup>，0 &le; C &le; 10；</p>
<p>对于70%的数据，3 &le; N &le; 10<sup>10</sup>，1 &le; X &le; 10<sup>10</sup>，0 &le; C &le; 100；</p>
<p>对于另30%的数据，3 &le; N &le; 10<sup>10</sup>，1 &le; X &le; 10<sup>10</sup>，0 &le; C &le; 1000，T = 1；</p>
<p>对于100%的数据，1 &le; T &le; 10，1 &le; s<sub>i</sub>,e<sub>i</sub> &le; N，s<sub>i</sub> &ne; e<sub>i</sub>，0 &le; t<sub>i</sub>，所有车辆的离开时间&nbsp;&le; X。</p>